package com.zhw.learning.recursion;

/**
 * @author zhw
 * 相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。
 * 该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。
 * 游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，
 *            并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
 */
public class TowerOfHanoi {

    public static void hanoi(int n, char a, char b, char c){
        if (n == 1){
            System.out.println("移动" + n + "号盘子从" + a + "到" + c);
        }
        else {
            // 把上面n-1个盘子从a借助b搬到c
            hanoi(n - 1, a, c, b);
            // 紧接着直接把n搬动c
            System.out.println("移动" + n + "号盘子从" + a + "到" + c);
            // 再把b上的n-1个盘子借助a搬到c
            hanoi(n - 1, b, a, c);
        }
    }

    public static void main(String[] args) {
        hanoi(4,'a','b','c');
    }

}
